/*************************************************************************
 * File Name:    Letter_Combination_of_a_Phone_Number.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/9 18:59:45
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Letter Combinations of a Phone Number
 | Given a digit string, return all possible letter combinations that the number could represent.
 |
 | A mapping of digit to letters (just like on the telephone buttons) is given below.
 |
 | Input:Digit string "23"
 | Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 | Note:
 | Although the above answer is in lexicographical order, your answer could be in any order you want.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits)
    {
        vector<string> ans;
        char str[digits.size() + 1];
        
        str[digits.size()] = '\0';
        dfs(ans, digits, 0, str);
        return ans;
    }

private:
    void dfs(vector<string> &ans, const string &digits, int p, char *str)
    {
        const char *dict[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        if (p == digits.size()) {
            ans.push_back(str);
            return;
        }
        for (const char *t = dict[digits[p] - '2']; *t != '\0'; ++t) {
            str[p] = *t;
            dfs(ans, digits, p + 1, str);
        }
    }
};

